package com.lwl.leetcode.notfinished;

import java.util.*;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/3/19 20:57
 */
public class Code30FindSubstring {
    public static void main(String[] args) {
//        String s = "barfoothefoobarman";
//        String[] words = {"foo", "bar"};
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","best","word"};
        List<Integer> list = findSubstring(s, words);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        if (words == null || words.length == 0) {
            return new ArrayList<>();
        }
        int step = words[0].length();
        int left = 0;
        char[] chars = s.toCharArray();
        Set<Integer> res = new HashSet<>();
        for (int right = step - 1; right < chars.length; right++) {
            if (right != left && (right - left + 1) % step == 0) {
                int index = matchUntilEnd(s, words, left, right);
                if (index != right) {
                    res.add(left);
                    left = index + 1;
                    right = index;
                } else {
                    left++;
                }
            }
        }
        return new ArrayList<>(res);
    }

    private static int matchUntilEnd(String s, String[] words, int left, int startRight) {
        int step = words[0].length();
        int right = left + step - 1;
        boolean isMatch = false;
        while (right < s.length() && checkSubString(s.substring(left, right + 1), words)) {
            isMatch = true;
            left = right + 1;
            right = left + step - 1;
        }
        return isMatch ? left + 1 : startRight;
    }

    private static boolean checkSubString(String str, String[] words) {
        String substring = str.substring(str.length() - words[0].length());
        for (String word : words) {
            if (substring.equals(word)) {
                return true;
            }
        }
        return false;
    }
}
